package TenkindsOfAlgorithm.greedyAlgorithm;
/**
 * 电台问题确实很烦 一个贪心算法
 */

import java.util.*;

public class CollectionMatch {
    public static void main(String[] args) {
        // 定义一个临时的集合，在遍历的过程中，存放遍历过程中电台覆盖地区与总城市的交集
        HashSet<String> tempSet = new HashSet<>();
        // 创建List存放电台集合
        ArrayList<String> list = new ArrayList<>();
        // 创建表示所有广播集合
        HashSet allAreas = new HashSet<String>();
        // 创建K-V 形式的对应关系
        HashMap<String, HashSet<String>> map = new HashMap<>();
        HashSet<String> set1 = new HashSet<String>();
        set1.add("beijing");
        set1.add("shanghai");
        set1.add("tianjin");
        HashSet<String> set2 = new HashSet<String>();
        set2.add("guangzhou");
        set2.add("beijing");
        set2.add("shenzhen");
        set2.add("shenzhen2");
        HashSet<String> set3 = new HashSet<String>();
        set3.add("chengdu");
        set3.add("shanghai");
        set3.add("hangzhou");
        HashSet<String> set4 = new HashSet<String>();
        set4.add("shanghai");
        set4.add("tianjin");
        HashSet<String> set5 = new HashSet<String>();
        set5.add("hangzhou");
        set5.add("dalian");
        map.put("K1",set1);
        map.put("K2",set2);
        map.put("K3",set3);
        map.put("K4",set4);
        map.put("K5",set5);
        for (Map.Entry<String,HashSet<String>> item : map.entrySet()){
            allAreas.addAll(item.getValue());
        }
        System.out.println(allAreas);
        HashSet<String> maxKeyAreas = new HashSet<>();
        while (allAreas.size()!=0){
            String maxKey = null;
            for (String key : map.keySet()){
                tempSet.clear();
                maxKeyAreas.clear();
                HashSet<String> value = map.get(key);
                tempSet.addAll(value);
                // 求出tempSet 和 allAreas集合的交集，赋值给tempSet
                tempSet.retainAll(allAreas);

                if (maxKey!=null){
                    maxKeyAreas.addAll(map.get(key));
                    maxKeyAreas.retainAll(allAreas);
                }
                if (tempSet.size()>0 && (maxKey==null || tempSet.size()> maxKeyAreas.size())){
                    maxKey = key;
                }
            }
            if (maxKey!=null){
                list.add(maxKey);
                allAreas.removeAll(map.get(maxKey));
            }
        }
        System.out.println(list
        );

    }

    public static void match() {

    }
}
